package com.hle;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Test {
	
	 public int findKthLargest(int[] nums, int k) {
	        // 小根堆，采样自下而上的建堆方式
	        for(int i = k/2-1; i >= 0; --i){
	            siftDown(nums, i, k);
	        }
	        for(int i = k; i < nums.length; ++i){
	            if(nums[i] <= nums[0]) continue;
	            nums[0] = nums[i];
	            siftDown(nums, 0, k);
	        }
	        return nums[0];
	    }

	     
	    private void siftDown(int[] nums,int index, int length) {
	        int element = nums[index];
	        int half = length >> 1;
	        while(index < half){
	            int childIndex = (index << 1) + 1;
	            int child = nums[childIndex];
	            int rightIndex = childIndex + 1;
	            if (rightIndex < length) {
	                if (nums[rightIndex] < child ) {
	                     child = nums[rightIndex];
	                     childIndex = rightIndex;
	                }
	            }
	            if (element <= child) break;
	            nums[index] = child;
	            index = childIndex;
	        }
	        nums[index] = element;
	    }
}




